/**
 * 998. 最大二叉树 II
 * https://leetcode-cn.com/problems/maximum-binary-tree-ii/
 */
public class Solutions_998 {
    public static void main(String[] args) {
        String str = "[4 1 3 # # 2]";
        int val = 5;  // output: [5 4 # 1 3 # # 2]

//        String str = "[5 2 4 # 1]";
//        int val = 3;  // output: [5 2 4 # 1 # 3]

//        String str = "[5 2 3 # 1]";
//        int val = 4;  // output: [5 2 4 # 1 3]

        TreeNode root = MyTreeNodeUtils.deserialize(str);
        TreeNode result = insertIntoMaxTree(root, val);
        System.out.println(MyTreeNodeUtils.serialize(result));
    }

    public static TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (root == null) {
            // 创建一个新节点，返回上层
            return new TreeNode(val);
        }
        if (root.val < val) {
            // val 比根节点值大，那么 cur 成为根节点，原本的 root 变成 cur 的左子树
            TreeNode cur = new TreeNode(val);
            cur.left = root;
            return cur;
        }
        // 递归解决子问题，右子树成为新的根节点，与 val 比较
        // root.right 接收返回的结果，并赋值
        root.right = insertIntoMaxTree(root.right, val);
        return root;
    }
}
